## The Gilbert-Varshamov lower bound

from PyM import *

def volume(n,r,q=2):
    v = 0
    b = q-1
    for i in range(r+1):
        v += binom(n,i) * b**i
    return v

def lb_gilbert(n,d,q=2):
    return int(ceil(q**n/volume(n,d-1,q)))

def lb_gilbert_varshamov(n,d,q=2):
    v = volume(n-1,d-2,q)
    k = 0
    while q**(n-k) > v:
        k += 1
    return q**(k-1)
    
show(lb_gilbert_varshamov(10,3)) # A(10,3) >= 64

show(lb_gilbert(10,3))